package huiwenzifuchuan;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
 *
 * 回文字符串 是正着读和倒过来读一样的字符串。
 *
 * 子字符串 是字符串中的由连续字符组成的一个序列。
 *
 * 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "abc"
 * 输出：3
 * 解释：三个回文子串: "a", "b", "c"
 * 示例 2：
 *
 * 输入：s = "aaa"
 * 输出：6
 * 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
 */
public class My647 {
    public int countSubstrings(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        int count = 0;
        List<String> palindromes = new ArrayList<>(); // 保存回文子串
        for (int i = 0; i < s.length(); i++) {
            count += judgeHuiWen(s, i, i, palindromes); // 回文中心是一个字符
            count += judgeHuiWen(s, i, i + 1, palindromes); // 回文中心是两个字符
        }
        System.out.println("回文子串为：" + palindromes);
        return count;
    }

    public int judgeHuiWen(String s, int begin, int end, List<String> palindromes) {
        int count = 0;
        while (begin >= 0 && end < s.length() && s.charAt(begin) == s.charAt(end)) {
            count++;
            palindromes.add(s.substring(begin, end + 1)); // 将回文子串加入列表
            begin--;
            end++;
        }
        return count;
    }

    public static void main(String[] args) {
        My647 my647 = new My647();
        int aa = my647.countSubstrings("aacbcaa");
        System.out.println("回文子串数量为：" + aa);
    }
}

